# 组合总和III: https://leetcode-cn.com/problems/combination-sum-iii/

# 我的写法，完全参照前面两题
class Solution:
    def combinationSum3(self, k: int, n: int):
        rst = [] 
        arr = [i for i in range(1, 10)] 
        def gTarget(nums, total, idx):
            if len(nums) == k:
                if total == 0:
                    rst.append(nums[:])
                return 
            
            for i in range(idx, len(arr)):
                nums.append(arr[i])
                gTarget(nums, total - arr[i], i + 1)
                nums.pop()
        
        gTarget([], n, 0)
        return rst


# 因为值就是 1-9， 不需要数组，idx 可以直接表示当前值
class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        rst = [] 
        def gTarget(nums, total, num):
            if len(nums) == k:
                if total == 0:
                    rst.append(nums[:])
                return 
            
            for i in range(num, 10):
                nums.append(i)
                gTarget(nums, total - i, i + 1)
                nums.pop()
        
        gTarget([], n, 1)
        return rst


s = Solution()
rst = s.combinationSum3(3, 9)
print(rst)

